home *** CD-ROM | disk | FTP | other *** search
/ Aminet 24 / Aminet 24 (1998)(GTI - Schatztruhe)[!][Apr 1998].iso / Aminet / comm / mail / Mutt089src.lha / Mutt-0.89i-AMIGA / src / rx / rxspencer.c < prev    next >
C/C++ Source or Header  |  1998-01-28  |  27KB  |  1,192 lines
  1. /*    Copyright (C) 1995, 1996 Tom Lord
  2.  * 
  3.  * This program is free software; you can redistribute it and/or modify
  4.  * it under the terms of the GNU Library General Public License as published by
  5.  * the Free Software Foundation; either version 2, or (at your option)
  6.  * any later version.
  7.  * 
  8.  * This program is distributed in the hope that it will be useful,
  9.  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  10.  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  11.  * GNU Library General Public License for more details.
  12.  * 
  13.  * You should have received a copy of the GNU Library General Public License
  14.  * along with this software; see the file COPYING.  If not, write to
  15.  * the Free Software Foundation, 59 Temple Place - Suite 330, 
  16.  * Boston, MA 02111-1307, USA. 
  17.  */
  18.  
  19.  
  20.  
  21. #include <stdio.h>
  22. #include "rxall.h"
  23. #include "rxspencer.h"
  24. #include "rxsimp.h"
  25.  
  26.  
  27.  
  28. static char * silly_hack_2 = 0;
  29.  
  30. struct rx_solutions rx_no_solutions;
  31.  
  32. #ifdef __STDC__
  33. struct rx_solutions *
  34. rx_make_solutions (struct rx_registers * regs, struct rx_unfaniverse * verse, struct rexp_node * expression, struct rexp_node ** subexps, int cset_size, int start, int end, rx_vmfn vmfn, rx_contextfn contextfn, void * closure)
  35. #else
  36. struct rx_solutions *
  37. rx_make_solutions (regs, verse, expression, subexps, cset_size, 
  38.            start, end, vmfn, contextfn, closure)
  39.      struct rx_registers * regs;
  40.      struct rx_unfaniverse * verse;
  41.      struct rexp_node * expression;
  42.      struct rexp_node ** subexps;
  43.      int cset_size;
  44.      int start;
  45.      int end;
  46.      rx_vmfn vmfn;
  47.      rx_contextfn contextfn;
  48.      void * closure;
  49. #endif
  50. {
  51.   struct rx_solutions * solns;
  52.  
  53.   if (   expression
  54.       && (expression->len >= 0)
  55.       && (expression->len != (end - start)))
  56.     return &rx_no_solutions;
  57.  
  58.   if (silly_hack_2)
  59.     {
  60.       solns = (struct rx_solutions *)silly_hack_2;
  61.       silly_hack_2 = 0;
  62.     }
  63.   else
  64.     solns = (struct rx_solutions *)malloc (sizeof (*solns));
  65.   if (!solns)
  66.     return 0;
  67.   rx_bzero ((char *)solns, sizeof (*solns));
  68.  
  69.   solns->step = 0;
  70.   solns->cset_size = cset_size;
  71.   solns->subexps = subexps;
  72.   solns->exp = expression;
  73.   rx_save_rexp (expression);
  74.   solns->verse = verse;
  75.   solns->regs = regs;
  76.   solns->start = start;
  77.   solns->end = end;
  78.   solns->vmfn = vmfn;
  79.   solns->contextfn = contextfn;
  80.   solns->closure = closure;
  81.  
  82.   if (!solns->exp || !solns->exp->observed)
  83.     {
  84.       solns->dfa = rx_unfa (verse, expression, cset_size);
  85.       if (!solns->dfa)
  86.     goto err_return;
  87.       rx_init_system (&solns->match_engine, solns->dfa->nfa);
  88.  
  89.       if (rx_yes != rx_start_superstate (&solns->match_engine))
  90.     goto err_return;
  91.     }
  92.   else
  93.     {
  94.       struct rexp_node * simplified;
  95.       int status;
  96.       status = rx_simple_rexp (&simplified, cset_size, solns->exp, subexps);
  97.       if (status)
  98.     goto err_return;
  99.       solns->dfa = rx_unfa (verse, simplified, cset_size);
  100.       if (!solns->dfa)
  101.     {
  102.       rx_free_rexp (simplified);
  103.       goto err_return;
  104.     }
  105.       rx_init_system (&solns->match_engine, solns->dfa->nfa);
  106.       if (rx_yes != rx_start_superstate (&solns->match_engine))
  107.     goto err_return;
  108.       rx_free_rexp (simplified);
  109.     }
  110.  
  111.   if (expression && (   (expression->type == r_concat)
  112.              || (expression->type == r_plus)
  113.              || (expression->type == r_star)
  114.              || (expression->type == r_interval)))
  115.     {
  116.       struct rexp_node * subexp;
  117.  
  118.       subexp = solns->exp->params.pair.left;
  119.  
  120.       if (!subexp || !subexp->observed)
  121.     {
  122.       solns->left_dfa = rx_unfa (solns->verse, subexp, solns->cset_size);
  123.     }
  124.       else
  125.     {
  126.       struct rexp_node * simplified;
  127.       int status;
  128.       status = rx_simple_rexp (&simplified, solns->cset_size, subexp, solns->subexps);
  129.       if (status)
  130.         goto err_return;
  131.       solns->left_dfa = rx_unfa (solns->verse, simplified, solns->cset_size);
  132.       rx_free_rexp (simplified);
  133.     }
  134.       
  135.       if (!solns->left_dfa)
  136.     goto err_return;
  137.       rx_bzero ((char *)&solns->left_match_engine, sizeof (solns->left_match_engine));
  138.       rx_init_system (&solns->left_match_engine, solns->left_dfa->nfa);
  139.     }
  140.   
  141.   return solns;
  142.  
  143.  err_return:
  144.   rx_free_rexp (solns->exp);
  145.   free (solns);
  146.   return 0;
  147. }
  148.  
  149.  
  150.  
  151. #ifdef __STDC__
  152. void
  153. rx_free_solutions (struct rx_solutions * solns)
  154. #else
  155. void
  156. rx_free_solutions (solns)
  157.      struct rx_solutions * solns;
  158. #endif
  159. {
  160.   if (!solns)
  161.     return;
  162.  
  163.   if (solns == &rx_no_solutions)
  164.     return;
  165.  
  166.   if (solns->left)
  167.     {
  168.       rx_free_solutions (solns->left);
  169.       solns->left = 0;
  170.     }
  171.  
  172.   if (solns->right)
  173.     {
  174.       rx_free_solutions (solns->right);
  175.       solns->right = 0;
  176.     }
  177.  
  178.   if (solns->dfa)
  179.     {
  180.       rx_free_unfa (solns->dfa);
  181.       solns->dfa = 0;
  182.     }
  183.   if (solns->left_dfa)
  184.     {
  185.       rx_terminate_system (&solns->left_match_engine);
  186.       rx_free_unfa (solns->left_dfa);
  187.       solns->left_dfa = 0;
  188.     }
  189.  
  190.   rx_terminate_system (&solns->match_engine);
  191.  
  192.   if (solns->exp)
  193.     {
  194.       rx_free_rexp (solns->exp);
  195.       solns->exp = 0;
  196.     }
  197.  
  198.   if (!silly_hack_2)
  199.     silly_hack_2 = (char *)solns;
  200.   else
  201.     free (solns);
  202. }
  203.  
  204.  
  205. #ifdef __STDC__
  206. static enum rx_answers
  207. rx_solution_fit_p (struct rx_solutions * solns)
  208. #else
  209. static enum rx_answers
  210. rx_solution_fit_p (solns)
  211.      struct rx_solutions * solns;
  212. #endif
  213. {
  214.   unsigned const char * burst;
  215.   int burst_addr;
  216.   int burst_len;
  217.   int burst_end_addr;
  218.   int rel_pos_in_burst;
  219.   enum rx_answers vmstat;
  220.   int current_pos;
  221.       
  222.   current_pos = solns->start;
  223.  next_burst:
  224.   vmstat = solns->vmfn (solns->closure,
  225.             &burst, &burst_len, &burst_addr,
  226.             current_pos, solns->end,
  227.             current_pos);
  228.  
  229.   if (vmstat != rx_yes)
  230.     return vmstat;
  231.  
  232.   rel_pos_in_burst = current_pos - burst_addr;
  233.   burst_end_addr = burst_addr + burst_len;
  234.  
  235.   if (burst_end_addr >= solns->end)
  236.     {
  237.       enum rx_answers fit_status;
  238.       fit_status = rx_fit_p (&solns->match_engine,
  239.                  burst + rel_pos_in_burst,
  240.                  solns->end - current_pos);
  241.       return fit_status;
  242.     }
  243.   else
  244.     {
  245.       enum rx_answers fit_status;
  246.       fit_status = rx_advance (&solns->match_engine,
  247.                    burst + rel_pos_in_burst,
  248.                    burst_len - rel_pos_in_burst);
  249.       if (fit_status != rx_yes)
  250.     {
  251.       return fit_status;
  252.     }
  253.       else
  254.     {
  255.       current_pos += burst_len - rel_pos_in_burst;
  256.       goto next_burst;
  257.     }
  258.     }
  259. }
  260.  
  261.  
  262. #ifdef __STDC__
  263. static enum rx_answers
  264. rx_solution_fit_str_p (struct rx_solutions * solns)
  265. #else
  266. static enum rx_answers
  267. rx_solution_fit_str_p (solns)
  268.      struct rx_solutions * solns;
  269. #endif
  270. {
  271.   int current_pos;
  272.   unsigned const char * burst;
  273.   int burst_addr;
  274.   int burst_len;
  275.   int burst_end_addr;
  276.   int rel_pos_in_burst;
  277.   enum rx_answers vmstat;
  278.   int count;
  279.   unsigned char * key;
  280.  
  281.  
  282.   current_pos = solns->start;
  283.   count = solns->exp->params.cstr.len;
  284.   key = (unsigned char *)solns->exp->params.cstr.contents;
  285.  
  286.  next_burst:
  287.   vmstat = solns->vmfn (solns->closure,
  288.             &burst, &burst_len, &burst_addr,
  289.             current_pos, solns->end,
  290.             current_pos);
  291.  
  292.   if (vmstat != rx_yes)
  293.     return vmstat;
  294.  
  295.   rel_pos_in_burst = current_pos - burst_addr;
  296.   burst_end_addr = burst_addr + burst_len;
  297.  
  298.   {
  299.     unsigned const char * pos;
  300.  
  301.     pos = burst + rel_pos_in_burst;
  302.  
  303.     if (burst_end_addr >= solns->end)
  304.       {
  305.     while (count)
  306.       {
  307.         if (*pos != *key)
  308.           return rx_no;
  309.         ++pos;
  310.         ++key;
  311.         --count;
  312.       }
  313.     return rx_yes;
  314.       }
  315.     else
  316.       {
  317.     int part_count;
  318.     int part_count_init;
  319.  
  320.     part_count_init = burst_len - rel_pos_in_burst;
  321.     part_count = part_count_init;
  322.     while (part_count)
  323.       {
  324.         if (*pos != *key)
  325.           return rx_no;
  326.         ++pos;
  327.         ++key;
  328.         --part_count;
  329.       }
  330.     count -= part_count_init;
  331.     current_pos += burst_len - rel_pos_in_burst;
  332.     goto next_burst;
  333.       }
  334.   }
  335. }
  336.  
  337.  
  338.  
  339.  
  340. #if 0
  341. #ifdef __STDC__
  342. int
  343. rx_best_end_guess (struct rx_solutions * solns, struct rexp_node *  exp, int bound)
  344. #else
  345. int
  346. rx_best_end_guess (solns, exp, bound)
  347.      struct rx_solutions * solns;
  348.      struct rexp_node *  exp;
  349.      int bound;
  350. #endif
  351. {
  352.   int current_pos;
  353.   unsigned const char * burst;
  354.   int burst_addr;
  355.   int burst_len;
  356.   int burst_end_addr;
  357.   int rel_pos_in_burst;
  358.   int best_guess;
  359.   enum rx_answers vmstat;
  360.  
  361. #if 0
  362.   unparse_print_rexp (256, solns->exp);
  363.   printf ("\n");
  364.   unparse_print_rexp (256, exp);
  365.   printf ("\nbound %d \n", bound);
  366. #endif
  367.  
  368.   if (rx_yes != rx_star